This invention relates to digital processing systems and more particularly to reducing the number of addressable memory locations and therefore the number of read-only memories (ROMs) required for numerical look-up table calculations while maintaining desired accuracy.
Memory look-up tables for performing arithmetic operations are well known in the state of the art. However, the number of memory locations or the number of read-only-memories (ROMs) required has often been a limiting function even though ROM capacity continually increases through technology advancement.
Various methods for reducing ROM capacity have been used. For example, elimination of the least significant bits reduces ROM storage requirements but results in a permanent loss of accuracy especially for small magnitudes. Another method is described in a patent of C. LeConte, U.S. Pat. No. 3,735,110 wherein a sine/cosine generator comprises a ROM which stores only the sine values of angles. A trigonometric identity is used to obtain cosine values thereby providing a reduction in the required amount of memory storage locations. In the patent of S. Lazecki, U.S. Pat. No. 3,917,935, the memory storage is reduced by first shifting input data bits, representative of the magnitude of numbers, to their more significant values whenever the magnitude of the largest of the two input numbers is less than that permitted by the maximum capacity of a system word, and using only some numbers of the shifted higher order data bits as the input address to a look-up table. This approach is applicable when calculating an arithmetic ratio of two numbers or for linear scaling but does not apply in general to numerical tables where the table output may or may not be used for ratio arithmetic.
In addition to table look-up techniques, another approach to finding the reciprocal of a number has been by trial and error consisting of subtracting, underflow, restore and shift in a repetitive sequence, but such approaches are extremely slow. In the patent of H. Sierra, U.S. Pat. No. 3,648,038, another technique for obtaining the reciprocal of a number is described using a flow-through technique employing combination logic and carry-save-adder trees, all of which requires considerable hardware.